times = 0
cache = {1: 1, 2: 1}


def fib(n):
    global times, cache
    times += 1
    if n in cache:
        return cache.get(n)
    else:
        result = fib(n - 1) + fib(n - 2)
        cache[n] = result
        return result


print(fib(999))
print(times)
